1. Field of the Invention
The invention concerns a technique which allows efficient implementation of self-checking arithmetic operators and data paths.
2. Background of the Related Art
Designing self-checking arithmetic units is a much more complex task than designing self-checking memory systems, register files, and shifters. Since arithmetic units (i.e. adders, ALUs, multipliers and dividers) are an essential element of computers, designing efficient self-checking arithmetic units is an important challenge in the area of self-checking and fault tolerant computers. That is why from the very early developments of fault tolerant computers an important amount of effort has been done on designing self-checking arithmetic units. The first designs are based on arithmetic residue codes (see in "PETERSON W. W. On checking an Adder, IBM J. Res. Develop. 2, pp.166-168, April 1958", in "PETERSON W. W., WELDON E. J., "Error-Correcting Codes", second Ed., The MIT press, Cambridge, Mass., 1972", in "AVIZIENIS A., Arithmetic Algorithms for Error-Coded Operands IEEE Trans. on Comput., Vol. C-22, No. 6, pp.567-572, June 1973"), and have been used in the JPL STAR Computer. Then parity prediction schemes has been given (see in "SELLERS F. F., HSIAO M.-Y. and BEARNSON L. W., Error Detecting Logic for Digital Computers, New-York: Mc GRAW-HILL 1968", and in "GARCIA O. N., RAO T. R. N., On the method of checking logical operations, Proc. 2nd Annual Princeton Conf. Inform. Sci. Sys., pp. 89-95 (1968)"), and more recently a Berger code prediction scheme has been proposed (see in LO J-C., THANAWASTIEN S., RAO T. R. N., NICOLAIDIS M. "An SFS Berger Check Prediction ALU and Its Application to Self-Checking Processors Designs" To appears in IEEE Transactions on CAD of ICAS).
Residue arithmetic codes are interesting for checking the arithmetic units since these codes are closed under arithmetic operations (i.e. if the operands belong to an arithmetic code the results of an arithmetic operation belong to this code too). However, they have the following drawbacks:
arithmetic code checkers are complex circuits, PA0 error detection in data path BUSes and Registers can be achieved by using the parity code, but in order to avoid complex code translators they also must be checked by the arithmetic code. This increase the area overhead of the whole data path. PA0 many errors due to single faults can be undetectable in carry lookahead adders checked by arithmetic codes (LANGDON G. G, TANG C. K. "Concurrent error detection for group look-ahead Binary Adders", IBM J. Res.Develop., pp.563-573, September 1970). PA0 logic operations are not closed under arithmetic codes and the use of residue arithmetic codes in ALUs requires complex circuit implementation for residue prediction. PA0 data paths based on residue codes are not compatible neither with self-checking memory systems (parity encoding), nor with fault tolerant memory systems (Hamming SEC/DED). PA0 it is self-checking for all the single faults, PA0 it requires a low hardware overhead (if possible lower than the one required by the parity prediction scheme), PA0 it is checked by a compact checker, and PA0 it can be combined with a parity checked data path without using code translators.
Parity prediction self-checking arithmetic units (see in "SELLERS F. F., HSIAO M.-Y. and BEARNSON L. W., Error Detecting Logic for Digital Computers, New-York: Mc GRAW-HILL 1968"), and logic units (see in "GARCIA O. N., RAO T. R. N., On the method of checking logical operations, Proc. 2nd Annual Princeton Conf. Inform. Sci. Sys., pp. 89-95 (1968)") have also been proposed. This scheme detects the single errors produced on the outputs of the arithmetic unit. Parity prediction arithmetic units require the lowest hardware overhead among all known self-checking arithmetic unit schemes. This scheme is compatible with parity checked data paths (which requires the minimum hardware overhead) and with parity encoded self-checking memory systems. It also can be modified to be compatible with Hamming SEC/DED memory systems (see "E. FUJIWARA, K. HARUTA Fault-tolerant Arithmetic Logic Unit Using Parity Based Codes. The transactions of the IECE of Japan, Vol E64, No. 10, October 1981". However, a single fault in an arithmetic unit can produce an error on a carry signal which can be propagated to several outputs of the arithmetic unit. Thus the parity scheme does not ensure the fault secure property for single faults.
The self-checking processor (SCP) described in (NANYA T., KAWAMURAT., "Error Secure/Propagation Concept and its Fault Secure Processors" IEEE Trans. on Comput., Vol. 37, No 1, pp. 14-24, January 1988) uses double-rail code for the data bus, the ALU and its associated accumulator and temporary registers. The register file is Berger encoded. Hence the data path requires one two-rail checker, one Berger code checker and two code translators. In order to improve this scheme, "LO J-C., THANAWASTIEN S., RAO T. R. N., NICOLAIDIS M. "An SFS Berger Check Prediction ALU and Its Application to Self-Checking Processors Designs" To appears in IEEE Transactions on CAD of ICAS" proposes to use a Berger code prediction ALU which avoids the use of translators. Thus the whole data path is checked by using a single Berger code checker per BUS. However, the whole data path must be encoded in the Berger code and thus the overhead is increased. Note also that the above schemes are not compatible with parity based self-checking memory systems or with Hamming SEC/DED fault tolerant memory systems.